1. Field of the Invention
The present invention relates to a congestion avoidance control system and method for a communication network, which, when it is desired to realize a tandem connection between various sorts of terminals connected through a plurality of exchanges and lines according to a route decision method for minimizing a communication cost, can relieve a call congestion to specific one of the exchanges to minimize the generation of a call loss.
2. Description of the Related Art
FIG. 1 shows a system configuration for explaining a prior art route decision method, in which a tandem connection between an outgoing terminal 100 and an incoming terminal 102 is carried out by selecting one of two routes, that is, one route leading from the outgoing terminal 100 to the incoming terminal 102 through an exchange 110, a line 120, an exchange 111, a line 121 and an exchange 112, and the other route leading from the terminal 100 to the terminal 102 through the exchange 110, a line 122, an exchange 113, a line 123 and the exchange 112.
The exchanges 110 to 113, which form a relay route for transmission of communication data, include connection type packet exchanges, connection type line exchanges, connection type asynchronous transfer mode exchanges and the like exchanges.
These sorts of exchanges 110 to 113 have respectively such a minimum cost table TBMCC as shown in FIG. 2 wherein a residual line capacity corresponding to its own full line capacity minus a line capacity being now used is divided into a plurality of different classes by predetermined capacity units and a line number L.sub.x providing a minimum cost from its own exchange to an incoming exchange (corresponding to the exchange 112 in the case of FIG. 1) is stored. The system selects one of routes leading from the outgoing terminal 100 to the incoming terminal 102 by making reference to the table TBMCC.
In FIG. 2, reference symbol N.sub.j denotes the number of an incoming exchange, [CN.sub.j, Cm] expressed in the form of [CN.sub.j, C1], [CN.sub.j, C2] and so on denotes a minimum cost for every line residual capacity class at the time of a tandem connection to the incoming exchange N.sub.j, and L.sub.xm expressed in the form of L.sub.x1, L.sub.x2 and so on denotes a line number providing a minimum cost to the line residual capacity class Cm.
The line residual capacity class Cm is, as shown in FIG. 3(a), expressed as divided into a plurality of stages of 0.ltoreq.Q&lt;B1, B1.ltoreq.Q&lt;B2, B2.ltoreq.Q&lt;B3 and so on corresponding to divisions of a line capacity Q by predetermined capacity units. For example, in class 1 corresponding to Cm=1, tandem connection can be carried out for a line capacity q less than the residual capacity B1.
Assume now that the line residual capacity class Cm is divided as shown in FIG. 3(b). Then a total cost CE.sub.x for a relay connection of an exchange E.sub.x and a relay line L.sub.i is expressed as follows. EQU CE.sub.x =.alpha.+.gamma.
where .alpha. represents a cost for each exchange E.sub.x when an exchange processing load and so on are taken into consideration and .gamma. represents a cost required for the route of the relay line L.sub.i (for example, .beta..times.DL.sub.i for a distance DL.sub.i, where .beta. is a distance cost coefficient).
More in detail, for example, when the processing cost .alpha. of the relay exchange E.sub.x is "0", the route cost (load) .gamma. for each line in the system of FIG. 1 is written as follows.
Line 120: .gamma.=5 PA1 Line 121: .gamma.=5 PA1 Line 122: .gamma.=10 PA1 Line 123: .gamma.=10 PA1 Line 120: Q=2 PA1 Line 121: Q=2 PA1 Line 122: Q=5 PA1 Line 123: Q=5
When the request line capacity q of the outgoing terminal 100 is 2 and the line residual capacities Q of the lines 120 to 123 are as follows,
and further when attention is directed to a route data of residual capacity class 2 for the incoming exchange 112, minimum cost tables 131-1, 132 and 130 stored in the exchanges 111, 113 and 110 have such data as shown in the respective tables in FIG. 1.
From the data of these tables, it will be appreciated that, when a calling request corresponding to residual capacity class 2 is issued, the system may select the line L.sub.2 (refer to the table 131-1) providing a minimum cost "5" from the exchange 111 to the exchange 112, the line L.sub.1 (refer to the table 132) providing a minimum cost "10" from the exchange 113 to the exchange 112, and the line L.sub.1 (refer to the table 130) providing a minimum cost "5+5" from the exchange 110 to the exchange 112.
Assuming now that a calling request having a line request capacity q is issued from the outgoing terminal 100 in the system of FIG. 1, then each of the exchanges 110 to 113 executes such a route deciding procedure as shown in FIG. 4. More specifically, each exchange first retrieves the minimum cost table TBMCC for each line residual capacity class and extracts the minimum cost line number L.sub.x corresponding to the line residual capacity class satisfying the line request capacity q (step 400).
Next, the exchange determines the minimum cost line L.sub.x as a minimum cost route leading to the incoming terminal 102 (step 410) and sends the calling request to the adjacent exchange connected downstream of the line L.sub.x (step 420).
The adjacent exchange, when receiving the calling request, carries out the same processing as the above and determines a minimum cost route leading to the incoming terminal 102.
More concretely, when a calling request having a line request capacity q=2 is issued from the outgoing terminal 100 to the incoming terminal 102, the exchange 110 selects the line L1 (line 120) corresponding to line residual capacity class 2 satisfying the line request capacity q=2 on the basis of the data of the minimum cost table 130.
The exchange 111 located downstream of the exchange 110 then selects the line L2 (line 121) corresponding to the line residual capacity class 2 on the basis of the data of the minimum cost table 131-1.
As a result, the outgoing terminal 100 is connected to the incoming terminal 102 via a route of exchange 110.fwdarw. line 120.fwdarw. exchange 111.fwdarw. line 121 exchange 112.
In this way, in the prior art route decision system, so long as a route satisfying the line request capacity of the outgoing terminal 100 is present, the outgoing terminal 100 and the incoming terminal 102 are interconnected via the route.
In order to realize such a route deciding procedure as mentioned above, it is necessary for each exchange to confirm the line residual capacity of the adjacent exchange and to prepare such a minimum cost table TBMCC for each line residual capacity class as shown in FIG. 2.
Explanation will next be made as how to prepare the minimum cost table TBMCC.
FIG. 5 is a flowchart showing the procedure of preparing the minimum cost table TBMCC, wherein two conditions (refer to step 530) are set as its procedure start timing when each line is varied in residual capacity or load and when constant period timing is provided.
When one exchange receives a calling request from an outgoing terminal and relays it to an exchange located downstream thereof, the downstream exchange is subjected to a change in the line capacity by an amount corresponding to the relay.
If the capacity change is large in such an extent that the line residual capacity class is to be shifted to another class, then the downstream exchange sends onto the input line L.sub.i of the upstream exchange such a minimum cost vector for the management of input line residual capacity showing a minimum cost value CN.sub.j, L.sub.i, Cm for each residual capacity class of lines leading to the incoming exchange N.sub.j as shown in FIG. 6.
The upstream exchange, when receiving the minimum cost vector for the management of input line residual capacity (step 500), updates to the then received minimum cost value [CN.sub.j,L.sub.i, Cm] the minimum cost value of the input line L.sub.i in an every-line minimum cost table TBMCL (refer to FIG. 7) showing the minimum cost values for all lines leading to the incoming exchange N.sub.j for different line residual capacity classes (step 510).
Then the exchange compares the minimum cost values listed in the column direction of the every-line minimum cost table TBMCL, extracts the line number L.sub.x for minimum cost connection to the incoming exchange N.sub.j and the associated minimum cost value for each line residual capacity class, and prepares such a minimum cost table TBMCC showing minimum costs for different line residual capacity classes as shown in FIG. 2 (step 520).
Thereafter, when the contents of the table TBMCC are changed, the exchange adds the current load values of all the lines L.sub.k except for the input line L.sub.i to the minimum cost values of all the lines L.sub.k and prepares such an output-line residual-capacity minimum-cost vector table TBMCL.sub.k as shown in FIG. 8 (steps 530 and 540).
Even when the contents of the table TBMCC are not changed, the processing of the step 540 is carried out in the constant-period data exchange timing mode.
In this constant-period timing mode, it goes without saying that the current load values of all the lines containing the input line L.sub.i are added.
Thereafter, the exchange sends the contents of the table TBMCL.sub.k (FIG. 8) prepared in the aforementioned manner onto the output line L.sub.k as a output-line residual-capacity minimum cost vector (step 550).
In this way, by discriminating minimum cost values for different line residual capacity classes of mutually adjacent exchanges through such data exchange and selecting a minimum cost route, the system can dynamically judge a minimum cost route to the incoming terminal while following variations in the loads of the exchanges.
In accordance with such prior art route decision procedure, for example, in the system of FIG. 1, when a calling request having a request capacity of 2 is generated from the outgoing terminal 100 and is to be sent therefrom to the incoming terminal 102, the calling request is determined to be sent from the outgoing terminal 100 to the incoming terminal 102 via a route of exchange 110.fwdarw. line 120.fwdarw. exchange 111.fwdarw. line 121.fwdarw. exchange 112, as already explained above.
In this case, after call setting between the outgoing and incoming terminals 100 and 102 is completed, the residual capacity classes of the lines 120 and 121 forming the then determined route are both decreased to class 1.
When this is considered from the viewpoint of data, the minimum cost table of the exchange 111 corresponds to a table 131-2 of the incoming exchange 112 relating to residual capacity class 2, which means that a minimum cost line from the exchange 111 to the exchange 112 corresponding to residual capacity class 2 is not present.
Under such a condition, if a calling request having a request capacity q=2 is issued from the outgoing terminal 101 to the incoming terminal 103, then the system cannot select any route and thus the calling request will result in a call loss at the exchange 111, since there is no route between the outgoing exchange 111 and incoming exchange 112 (since the minimum cost table of the exchange 111 is as shown by the table 131-2).
As will be clear from the system configuration of FIG. 1, the outgoing terminal 101 can have only the line 121 in order to be connected with the incoming terminal 103, and in other words, the terminal 101 has no route selection.
Accordingly, the line 121 must previously be left for communication between the outgoing and incoming terminals 101 and 103.
In spite of such a requirement, this sort of prior art route decision system has paid attention only to the line residual capacity and been arranged so that a minimum cost line is selected with no consideration paid at all to the secured route for such a terminal that is impossible to realize a route to the incoming terminal without selection of the mere line (such as the line 121), e.g., the route of the outgoing terminal 101.
For this reason, the prior art route decision system has had such a trouble that, when calling requests are converged on a particular exchange, this causes a call loss to be increased so that the system tends to be put to its congestion state, thereby impeding the effective operation of the system.
In the aforementioned prior art route decision system, in this way, when a calling request is issued from an outgoing terminal to an incoming terminal, the system selects minimum cost one of possible routes of lines which lead from the outgoing exchange to the incoming exchange and which line residual capacities satisfy the request capacity of the outgoing terminal.
This, after the completion of a call setting, results in that the residual capacities of lines forming the selected route are decreased by an amount corresponding to the request capacity of the outgoing terminal. At this time, when the residual capacity of any one of the lines forming the minimum cost route corresponds nearly to the request capacity of the outgoing terminal, the residual capacity of that line forming the selected minimum cost route becomes substantially zero during communication through the selected route.
Under such a condition, if an calling request having a request capacity beyond the residual capacity of that line forming the relay route is issued from a terminal connected to the associated exchange in the relay route, then even the selection of that line disables the setting of a route. In addition, when the request issuing terminal cannot secure any other route without that line, the calling request from the outgoing terminal inevitably results in a call break and a call loss.
In this way, the prior art route decision system has had such a problem that, since no consideration is taken at all to securing a route for such a terminal that cannot set a route to an incoming terminal without selection of such a line, a call loss frequently takes place and the system tends to be put in the congestion state, thus resulting in that the system cannot be efficiently operated.